// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked - list - cycle - ii/
public class Code05_LinkedListCycleII {
    // 不要提交这个类，这是内部辅助类，用于表示链表节点
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 提交如下的方法，用于检测链表是否存在环并返回环的第一个入环节点
    public static ListNode detectCycle(ListNode head) {
        // 先处理特殊情况，如果链表为空或者链表只有1个或2个节点，肯定不存在环，直接返回null
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }

        // 定义慢指针，初始化为头节点的下一个节点
        ListNode slow = head.next;
        // 定义快指针，初始化为头节点的下一个节点的下一个节点
        ListNode fast = head.next.next;

        // 快慢指针同时移动，快指针每次移动两步，如果快指针没有与慢指针相遇且快指针没有走到链表末尾
        // 就继续移动
        while (slow!= fast) {
            // 如果快指针的下一个节点为null或者快指针的下一个节点的下一个节点为null
            // 说明链表不存在环，直接返回null
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            // 慢指针移动一步
            slow = slow.next;
            // 快指针移动两步
            fast = fast.next.next;
        }

        // 当快慢指针相遇时，说明存在环，此时将快指针重新指向链表的头节点
        fast = head;
        // 然后快慢指针以相同的速度（每次移动一步）再次移动
        while (slow!= fast) {
            // 慢指针移动一步
            slow = slow.next;
            // 快指针移动一步
            fast = fast.next;
        }

        // 当快慢指针再次相遇时，这个相遇的节点就是环的第一个入环节点，返回该节点
        return slow;
    }
}